package com.wenx.common;

import java.util.Arrays;

/**
 * 爬楼梯算法，与菲波那切数列相似
 * Created by wenx on 2019-10-10 14:48
 */
public class ClimbStairs {

    public static void main(String[] args) {
        ClimbStairs climbStairs = new ClimbStairs();
        int i = climbStairs.climbStairs(5);
        System.out.println("i = " + i);
    }

    int getClimbStairs(int n) {
        if(n == 1)
            return 1;
        if(n ==2)
            return 2;
        return getClimbStairs(n-1) + getClimbStairs(n-2);
    }


    int climbStairs(int n) {
        int[] memo= new int[n + 1];
        Arrays.fill(memo, -1);

        memo[0] = 1;
        memo[1] = 1;

        for (int i = 2; i <= n; i++)
            memo[i] = memo[i - 1] + memo[i - 2];

        return memo[n];
    }

}